﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
using System.Collections;

namespace Graph
{
    abstract class BaseGraph
    {
        public abstract class Cycle
        {
            public enum Direction
            {
                LEFT, RIGHT
            }

            public int Begin { get; protected set; }
            public List<int> Vertexes { get; protected set; }

            public Cycle(int begin, LinkedList<int> vertexes)
            {
                vertexes.AddFirst(begin);
                Vertexes = vertexes.ToList();
                Normalize();
            }

            private void Normalize()
            {
                int indexMin = 0;
                for (int i = 0; i < Vertexes.Count; ++i)
                {
                    if (Vertexes[i] < Vertexes[indexMin])
                    {
                        indexMin = i;
                    }
                }
                Begin = Vertexes[indexMin];

                Direction d = ChooseDirection(indexMin);
                if (indexMin == 0)
                {
                    if (d == Direction.RIGHT)
                    {
                        Vertexes.RemoveAt(0);
                    }
                    else // LEFT
                    {
                        Vertexes.Reverse();
                        Vertexes.Remove(Vertexes.Count - 1);
                    }
                    return;
                }

                List<int> newVertexes = new List<int>(Vertexes.Count);
                int index = indexMin;
                if (d == Direction.RIGHT)
                {
                    for (int i = 1; i < Vertexes.Count; ++i)
                    {
                        ++index;
                        if (index >= Vertexes.Count) index = 0;
                        newVertexes.Add(Vertexes[index]);
                    }
                }
                else // LEFT
                {
                    for (int i = 1; i < Vertexes.Count; ++i)
                    {
                        --index;
                        if (index < 0) index = Vertexes.Count;
                        newVertexes.Add(Vertexes[index]);
                    }
                }
                Vertexes = newVertexes;
            }

            protected abstract Direction ChooseDirection(int indexMin);

            public override string ToString()
            {
                return ToString("-");
            }

            public string ToString(string seperator)
            {
                StringBuilder strBuilder = new StringBuilder(Vertexes.Count + (Vertexes.Count - 1) * seperator.Length);
                strBuilder.Append(Begin).Append(seperator);
                foreach (int vertex in Vertexes)
                    strBuilder.Append(vertex).Append(seperator);
                strBuilder.Append(Begin);
                return strBuilder.ToString();
            }
        }

        public class CycleComparer : EqualityComparer<Cycle>, IComparer<Cycle>
        {
            public int DoCompare(Cycle x, Cycle y)
            {
                if (x == null && y == null) return 0;
                if (x == null) return -1;
                if (y == null) return 1;
                //
                if (x.Begin != y.Begin) return x.Begin - y.Begin;
                //
                IEnumerator<int> xer = x.Vertexes.GetEnumerator();
                IEnumerator<int> yer = y.Vertexes.GetEnumerator();
                while (true)
                {
                    bool xHasNext = xer.MoveNext();
                    bool yHasNext = yer.MoveNext();
                    if (!xHasNext && !yHasNext) return 0;
                    if (!xHasNext) return -1;
                    if (!yHasNext) return 1;
                    //
                    if (xer.Current != yer.Current) return xer.Current - yer.Current;
                }
            }

            public override bool Equals(Cycle x, Cycle y)
            {
                return DoCompare(x, y) == 0;
            }

            public override int GetHashCode(Cycle obj)
            {
                int hashCode = obj.Begin + obj.Vertexes.Sum();
                return hashCode;
            }

            int IComparer<Cycle>.Compare(Cycle x, Cycle y)
            {
                return DoCompare(x, y);
            }
        }

        public BaseGraph(string filePath)
        {
            buildGraph(filePath);
        }

        public int getNVertexes()
        {
            return numVertex;
        }

        protected void buildGraph(string filePath)
        {
            try
            {
                using (System.IO.StreamReader file = new System.IO.StreamReader(filePath))
                {
                    // read the number of vertexes
                    readTheNumberOfVertexes(file);

                    this.vertexs = new Dictionary<string, Vertex>(this.numVertex);
                    this.vertexsByKey = new Dictionary<int, Vertex>(this.numVertex);
                    for (int i = 0; i < this.numVertex; i++)
                    {
                        Vertex v = new Vertex("" + i, i);
                        this.vertexs.Add(v.Label, v);
                        this.vertexsByKey.Add(v.Key, v);
                    }

                    // read each line
                    adjMatrix = new int[numVertex, numVertex];
                    initMatrix();
                    string line = null;
                    for (int icurVertex = 0; icurVertex < this.numVertex && (line = file.ReadLine()) != null; ++icurVertex)
                    {
                        if (string.IsNullOrWhiteSpace(line)) continue;
                        Vertex v1 = this.vertexs["" + icurVertex];
                        string[] adjVertexes = line.Split(' ');
                        for (int j = 0; j < adjVertexes.Length; ++j)
                        {
                            if (string.IsNullOrWhiteSpace(adjVertexes[j])) continue;
                            adjVertexes[j] = adjVertexes[j].Trim();
                            try
                            {
                                Vertex v2 = this.vertexs[adjVertexes[j]];
                                addToAdjMatrix(v1, v2);
                            }
                            catch (Exception ex)
                            {
                                if (!Program.ConsoleMode)
                                    MessageBox.Show(ex.Message + "\n" + "Vertex is reading " + adjVertexes[j], "Error in build Graph", MessageBoxButtons.OK, MessageBoxIcon.Error);
                                continue;
                            }
                        }
                    }
                }

                int estimatedCyclesNumber = 0;
                for (int i = 0, estimatedNumberi = 1; i < numVertex; ++i, estimatedNumberi *= 4)
                    estimatedCyclesNumber += estimatedNumberi;
                cycles = new List<Cycle>(estimatedCyclesNumber);
            }
            catch (Exception ex)
            {
                if (!Program.ConsoleMode)
                    MessageBox.Show(ex.Message, "Error in buildGraph()", MessageBoxButtons.OK, MessageBoxIcon.Error);
                else
                    Environment.Exit(-1);
            }
        }

        private void initMatrix()
        {
            if (adjMatrix == null) return;
            for (int i = 0; i < numVertex; i++)
            {
                for (int j = 0; j < numVertex; j++)
                {
                    adjMatrix[i, j] = 0;
                }
            }
        }

        private void readTheNumberOfVertexes(System.IO.StreamReader file)
        {
            string line = null;
            this.numVertex = -1;
            do
            {
                line = file.ReadLine();
                if (line == null)   // reach end of file
                {
                    throw new System.IO.IOException("Empty file");
                }
            }
            while (string.IsNullOrWhiteSpace(line));
            //
            this.numVertex = int.Parse(line);
            if (this.numVertex <= 0)
                throw new System.IO.InvalidDataException(string.Format("nvertex ({0}) <= 0", this.numVertex));
        }

        protected abstract void addToAdjMatrix(Vertex v1, Vertex v2);

        protected abstract void DFS(Vertex begin);

        public virtual List<Cycle> findAllCycles()
        {
            if (vertexs != null)
            {
                foreach (KeyValuePair<string, Vertex> entry in this.vertexs)
                {
                    DFS(entry.Value);
                    //resetGraph();
                }
            }
            cycles.Sort(CycleCmper);
            return cycles;
        }

        protected Cycle trackCycle(Vertex end, Vertex begin)
        {
            //track list vertex in cycle fom begin to end
            LinkedList<int> vertexes = new LinkedList<int>();
            vertexes.AddLast(end.Key);
            Vertex tmp = end.Father;
            //Vertex tmp2 = end;
            while (tmp != null)
            {
                if (tmp.equal(begin))
                {
                    break;
                }
                vertexes.AddFirst(tmp.Key);
                tmp = tmp.Father;
                if (tmp == null) {
                    return null;
                }
            }
            //vertexes.AddFirst(begin.Key); // done in building final cycle string
            //vertexes.AddLast(begin.Key); // done in building final cycle string

            return NewCycle(begin.Key, vertexes);
        }

        protected abstract Cycle NewCycle(int begin, LinkedList<int> vertexes);

        protected void resetGraph()
        {
            if (vertexs != null)
            {
                foreach (KeyValuePair<string, Vertex> entry in this.vertexs)
                {
                    entry.Value.Color = VertexColor.WHITE;
                    entry.Value.D = 0;
                    entry.Value.F = 0;
                    entry.Value.Father = null;
                }
            }
            if (vertexsByKey != null)
            {
                foreach (KeyValuePair<int, Vertex> entry in this.vertexsByKey)
                {
                    entry.Value.Color = VertexColor.WHITE;
                    entry.Value.D = 0;
                    entry.Value.F = 0;
                    entry.Value.Father = null;
                }
            }
        }

        protected List<Vertex> getAdjOfVertex(Vertex v)
        {
            List<Vertex> ret = new List<Vertex>();
            int indexOfV = v.Key;
            for (int i = 0; i < numVertex; i++)
            {
                if (adjMatrix[indexOfV, i] > 0)
                {
                    Vertex u = this.vertexsByKey[i];
                    ret.Add(u);
                }
            }
            return ret;
        }

        public void printAllCyclesToFile(string filePath)
        {
            using (StreamWriter sw = new StreamWriter(filePath))
            {
                if (cycles == null || cycles.Count <= 0)
                {
                    string strNumOfCycle = "0" + new string(' ', LENGTH_FOR_NUM_OF_CYCLE - 1);
                    sw.WriteLine(strNumOfCycle);
                }
                else
                {
                    string strNumOfCycle = cycles.Count.ToString("#,##0");
                    strNumOfCycle += new string(' ', LENGTH_FOR_NUM_OF_CYCLE - strNumOfCycle.Length);
                    sw.WriteLine(strNumOfCycle);
                    foreach (Cycle cycle in cycles)
                    {
                        sw.WriteLine(cycle);
                    }
                }
            }
        }

        protected Dictionary<string, Vertex> vertexs = null;
        protected Dictionary<int, Vertex> vertexsByKey = null;
        protected int[,] adjMatrix = null;
        protected int numVertex = 0;
        protected List<Cycle> cycles = null;
        //
        protected int time = 0;
        //
        protected static CycleComparer CycleCmper = new CycleComparer();
        protected const int LENGTH_FOR_NUM_OF_CYCLE = 20;
    }
}
